package top.swimmer.tools.tree;

public class BinaryTree<KEY extends Comparable<KEY>, VALUE> {

    private Node root;

    public VALUE get(KEY key) {
        return get(root, key);
    }

    public void put(KEY key, VALUE value) {
        root = put(root, key, value);
    }

    private void forPut(KEY key, VALUE value) {
        if (root == null) {
            root = new Node(key, value, 1);
            return;
        }
        Node current = root;

        while (true) {
            int order = key.compareTo(current.key);
            if (order < 0) {
                if (current.left == null) {
                    current.left = new Node(key, value, 1);
                    return;
                }
                current = current.left;
            } else {
                if (current.right == null) {
                    current.right = new Node(key, value, 1);
                    return;
                }
                current = current.right;
            }
        }
    }

    private Node put(Node node, KEY key, VALUE value) {
        if (node == null) {
            return new Node(key, value, 1);
        }

        int order = key.compareTo(node.key);
        if (order < 0)
            node.left = put(node.left, key, value);
        else if (order > 0)
            node.right = put(node.right, key, value);
        else
            node.value = value;
        node.number = size(node.left) + size(node.right) + 1;
        return node;
    }

    private int size(Node node) {
        return node == null ? 0 : node.number;
    }

    private VALUE get(Node root, KEY key) {
        VALUE result = null;
        Node node = root;
        while (node != null) {
            if (key.compareTo(node.key) > 0) {
                node = node.right;
            } else if (key.compareTo(node.key) < 0) {
                node = node.left;
            } else {
                result = node.value;
                break;
            }
        }
        return result;
    }

    private class Node {
        Node left;
        Node right;
        int number;
        KEY key;
        VALUE value;

        public Node(KEY key, VALUE value, int number) {
            this.number = number;
            this.key = key;
            this.value = value;
        }
    }
}
